import Node from "./type";
import { btPrint } from "hy-algokit";

class TreeNode<T> extends Node<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  parent?: TreeNode<T> | null = null;

  //是否是左子节点
  get isLeft(): boolean {
    return !!(this.parent && this.parent.left === this);
  }

  //是否是右子节点
  get isRight(): boolean {
    return !!(this.parent && this.parent.right === this);
  }
}

//二叉搜索树
class BinarySearchTree<T> {
  private root: TreeNode<T> | null = null;

  //递归插入
  private insertNode(root: TreeNode<T>, newNode: TreeNode<T>) {
    if (newNode.value < root.value) {
      //左子树
      if (!root.left) {
        root.left = newNode;
      } else {
        this.insertNode(root.left, newNode);
      }
    } else {
      //右子树
      if (!root.right) {
        root.right = newNode;
      } else {
        this.insertNode(root.right, newNode);
      }
    }
  }

  //插入操作
  insert(value: T) {
    const newNode = new TreeNode<T>(value);

    if (!this.root) {
      //无根节点
      this.root = newNode;
    } else {
      //有根节点
      this.insertNode(this.root, newNode);
    }
  }

  //打印
  print() {
    btPrint(this.root);
  }

  //先序遍历递归
  private preOrderTraverseLoop(root: TreeNode<T> | null) {
    if (root) {
      console.log(root.value);
      this.preOrderTraverseLoop(root.left);
      this.preOrderTraverseLoop(root.right);
    }
  }
  //先序遍历
  preOrderTraverse() {
    this.preOrderTraverseLoop(this.root);
  }

  //中序遍历递归
  private inOrderTraverseLoop(root: TreeNode<T> | null) {
    if (root) {
      this.inOrderTraverseLoop(root.left);
      console.log(root.value);
      this.inOrderTraverseLoop(root.right);
    }
  }
  //中序遍历
  inOrderTraverse() {
    this.inOrderTraverseLoop(this.root);
  }

  //后序遍历递归
  private postTraverseLoop(root: TreeNode<T> | null) {
    if (root) {
      this.postTraverseLoop(root.left);
      this.postTraverseLoop(root.right);
      console.log(root.value);
    }
  }
  //后序遍历
  postOrderTraverse() {
    this.postTraverseLoop(this.root);
  }

  //层序遍历
  levelOrderTraverse() {
    if (!this.root) return;

    //根节点入栈
    const queue: TreeNode<T>[] = [];
    queue.push(this.root);

    //根节点出栈，同时左节点和右节点入栈
    while (queue.length) {
      const node = queue.shift();
      node?.left && queue.push(node?.left);
      node?.right && queue.push(node?.right);
    }
  }

  //获取最大值
  getMaxValue(): T | null {
    //一直往右节点找
    if (!this.root) return null;
    let current = this.root;
    while (current && current.right) {
      current = current.right;
    }
    return current.value;
  }

  //获取最小值
  getMinValue(): T | null {
    //一直往左节点找
    if (!this.root) return null;
    let current = this.root;
    while (current && current.left) {
      current = current.left;
    }
    return current.value;
  }

  //searchNode
  private searchNode = (root: TreeNode<T> | null, value: T): TreeNode<T> | null => {
    if (!root) return root;
    let current: TreeNode<T> | null = this.root;
    let parent: TreeNode<T> | null = null;

    while (current) {
      if (current.value === value) {
        return current;
      } else if (current.value < value) {
        parent = current;
        current = current.right;
      } else {
        parent = current;
        current = current.left;
      }
      if (current) {
        current.parent = parent;
      }
    }
    return null;
  };

  //搜索元素
  search(value: T): boolean {
    return !!this.searchNode(this.root, value);
  }

  //寻找后驱节点
  private getSuccessor(delNode: TreeNode<T>): TreeNode<T> | null {
    //获取右子树
    let current = delNode.right;
    let successor: TreeNode<T> | null = null;
    while (current) {
      successor = current;
      current = current.left;
      if (current) {
        current.parent = successor;
      }
    }

    if (successor?.right !== delNode.right) {
      successor!.parent!.left = successor!.right;
      successor!.right = delNode.right;
    }

    //将删除的节点left，赋值给后继节点的left
    successor!.left = delNode.left;
    return successor;
  }

  //删除元素
  remove(value: T) {
    //获取当前节点
    let currentNode: TreeNode<T> | null = this.searchNode(this.root, value);
    //要删除的节点不在树结构中
    if (!currentNode) return false;
    //判断是否是叶节点
    if (!currentNode.left && !currentNode.right) {
      if (currentNode === this.root) {
        //根节点
        this.root = null;
      } else if (currentNode.isLeft) {
        //左子节点
        currentNode.parent!.left = null;
      } else {
        //右子节点
        currentNode.parent!.right = null;
      }
    }
    //只有左节点
    else if (currentNode.right === null) {
      if (this.root === currentNode) {
        //被删除的是根节点
        this.root = currentNode.left;
      } else {
        currentNode.parent!.left = currentNode.left;
      }
    }
    //只有右节点
    else if (currentNode.left === null) {
      if (this.root === currentNode) {
        //被删除的是根节点
        this.root = currentNode.right;
      } else {
        currentNode.parent!.right = currentNode.right;
      }
    }
    //左右节点都有
    else {
      //找到前驱节点或者后继节点，去替换要删除的节点
      const successorNode = this.getSuccessor(currentNode);

      if (currentNode === this.root) {
        this.root = successorNode;
      } else if (currentNode.isLeft) {
        currentNode.parent!.left = successorNode;
      } else {
        currentNode.parent!.right = successorNode;
      }
    }
  }
}

const BSTree = new BinarySearchTree();

BSTree.insert(11);
BSTree.insert(7);
BSTree.insert(15);
BSTree.insert(5);
BSTree.insert(3);
BSTree.insert(9);
BSTree.insert(8);
BSTree.insert(10);
BSTree.insert(13);
BSTree.insert(12);
BSTree.insert(14);
BSTree.insert(20);
BSTree.insert(18);
BSTree.insert(25);
BSTree.insert(6);

//先序遍历
// BSTree.preOrderTraverse();

//中序遍历
// BSTree.inOrderTraverse();

//后序遍历
// BSTree.postOrderTraverse();

//层序遍历
// BSTree.levelOrderTraverse();

//最大值 最小值
// console.log(`最大值:${BSTree.getMaxValue()}`, `最小值：${BSTree.getMinValue()}`);

//搜索
// console.log(BSTree.search(35));
// console.log(BSTree.search(17));

// console.log(BSTree.search(10));
// console.log(BSTree.search(6));

//删除叶节点m
// BSTree.remove(6);
// BSTree.remove(10);
// BSTree.remove(14);
// BSTree.remove(25);

// BSTree.print();

// BSTree.remove(3);
// BSTree.remove(5);
// BSTree.print();

//删除左子叶节点
// BSTree.remove(6);
// BSTree.remove(10);
// BSTree.remove(14);
// BSTree.remove(25);
// BSTree.print();

// BSTree.remove(5);
// BSTree.print();

//删除右子叶节点
// BSTree.remove(3);
// BSTree.remove(8);
// BSTree.remove(12);
// BSTree.remove(18);
// BSTree.print();
// BSTree.remove(9);
// BSTree.remove(20);

//删除左右子叶的节点
BSTree.remove(15);

BSTree.print();

export {};
